

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution
{
    using Node = TreeNode;
    using PII = pair<int, int>;

public:
    TreeNode* balanceBST(TreeNode* root)
    {
        vector<int> v;
        v.reserve(1e4);

        _Inorder(root, v);

        return _AVLTree(v, 0, v.size() - 1);
    }

    
public:
    vector<int> topKFrequent1(vector<int>& nums, int k)
    {
        vector<PII> vp;
        vector<int> res;
        unordered_map<int, int> kv;

        for (const auto e : nums)
        {
            ++kv[e];
        }
        for (const auto e : kv)
        {
            vp.push_back(e);
        }

        sort(vp.begin(), vp.end(), comp());
        // c++17
        /*for (auto [x, y] : vp)
        {
            res.push_back(x);
        }*/
        for (const auto e : vp)
        {
            res.push_back(e.first);
        }

        return vector<int>(res.begin(), res.begin() + k);
    }

    vector<int> topKFrequent2(vector<int>& nums, int k)
    {
        vector<int> res;
        res.reserve(k);
        unordered_map<int, int> kv;
        priority_queue<PII, vector<PII>, comp> q;

        for (const auto e : nums)
        {
            ++kv[e];
        }

        auto it = kv.begin();
        for (int i = k; i--; ++it)
        {
            q.push(*it);
        }

        while (it != kv.end())
        {
            if (it->second > q.top().second)
            {
                q.pop();
                q.push(*it);
            }
            ++it;
        }

        while (q.size())
        {
            res.push_back(q.top().first);
            q.pop();
        }

        return res;
    }

    // err
    vector<int> topKFrequent3(vector<int>& nums, int k)
    {
        vector<int> res;
        vector<PII> vp;
        unordered_map<int, int> kv;

        srand(time(nullptr));
        res.reserve(1e5);

        for (auto e : nums)
        {
            ++kv[e];
        }
        for (const auto& e : kv)
        {
            vp.push_back(e);
        }

        _topKFrequent(vp, k, res, 0, vp.size() - 1);

        return res;
    }

private:
    void _Inorder(Node* root, vector<int>& v)
    {
        if (!root)
            return;

        _Inorder(root->left, v);
        v.push_back(root->val);
        _Inorder(root->right, v);
    }

    Node* _AVLTree(const vector<int>& v, int lf, int rg)
    {
        if (lf > rg)
            return nullptr;

        int mid = lf + ((rg - lf) >> 1);
        Node* root = new Node(v[mid]);

        root->left = _AVLTree(v, lf, mid - 1);
        root->right = _AVLTree(v, mid + 1, rg);

        return root;
    }

    void _topKFrequent(vector<PII>& vp, int k, vector<int>& res, int lf, int rg)
    {
        if (k <= 0)
            return;

        int keyi = rand() % (rg - lf + 1) + lf;
        swap(vp[lf], vp[keyi]);

        int key_val = vp[lf].second;
        int prev = lf, cur = lf + 1;

        while (cur <= rg)
        {
            if (vp[cur].second >= key_val && ++prev != cur)
            {
                swap(vp[prev], vp[cur]);
            }
            ++cur;
        }
        swap(vp[lf], vp[prev]);

        if (k <= prev - lf)
        {
            _topKFrequent(vp, k, res, lf, prev - 1);
        }
        else
        {
            for (int i = lf; i <= prev; ++i)
            {
                res.push_back(vp[i].first);
            }
            _topKFrequent(vp, k - (prev - lf + 1), res, ++prev, rg);
        }
    }

    struct comp
    {
        bool operator()(const PII& x, const PII& y)
        {
            return x.second > y.second;
        }
    };
};

void Test1()
{
    int k = 2;
    vector<int> v{ 1,1,1,2,2,3 };

    Solution().topKFrequent3(v, k);
}

int main()
{
    Test1();


	return 0;
}